package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode

/**
 * @author flutterdash@qq.com
 * @since 2021/4/8 21:56
 */
class P07 {

    /**
     * preorder: 3, 9, 20, 15, 7
     * inorder : 9, 3, 15, 20, 7
     *
     *        3
     *      /  \
     *     9    20
     *         /  \
     *        15   7
     */
    private fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        fun buildTree(preStart: Int, preBound: Int, inStart: Int, inBound: Int): TreeNode? {
            if (preStart > preBound) return null
            val root = TreeNode(preorder[preStart])
            if (preStart == preBound)
                return root
            val pivot = root.`val`
            var pos = preStart
            for (idx in inStart..inBound) {
                if (inorder[idx] == pivot) {
                    pos = idx
                    break
                }
            }
            val leftSubTreeSize = pos - inStart
            root.left = buildTree(preStart + 1, preStart + leftSubTreeSize, inStart, pos - 1)
            root.right = buildTree(preStart + leftSubTreeSize + 1, preBound, pos + 1, inBound)
            return root
        }

        if (preorder.isEmpty()) return null
        return buildTree(0, preorder.size - 1, 0, inorder.size - 1)
    }

    @Test
    fun test0() {
        val root = buildTree(intArrayOf(3, 9, 20, 15, 7), intArrayOf(9, 3, 15, 20, 7))
        print(root)
    }

}
